package Hot100.Medium.BinaryTree;

import Hot100.Easy.LC104.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class LC105_BuildTree {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 创建中序遍历的值->索引映射，便于快速查找根节点位置
        Map<Integer, Integer> index = new HashMap<>(n, 1);
        for (int i = 0; i < n; i++) {
            index.put(inorder[i], i);  // 值 -> 在中序遍历中的索引
        }
        // 调用递归函数，使用左闭右开区间 [start, end)
        return dfs(preorder, 0, n, 0, n, index);
    }

    private TreeNode dfs(int[] preorder, int preL, int preR,
                         int inL, int inR, Map<Integer, Integer> index) {

        // 递归终止条件：范围为空
        if (preL == preR) {
            return null;
        }

        // 前序遍历的第一个元素就是当前子树的根节点
        int rootVal = preorder[preL];

        // 在中序遍历中找到根节点的位置
        int rootIndexInInorder = index.get(rootVal);

        // 计算左子树的大小（中序遍历中根节点左边的元素个数）
        int leftSize = rootIndexInInorder - inL;

        // 递归构建左子树
        // 前序遍历：从 preL+1 开始，取 leftSize 个元素
        // 中序遍历：从 inL 开始，到根节点之前
        TreeNode left = dfs(preorder, preL + 1, preL + 1 + leftSize,
                inL, inL + leftSize, index);

        // 递归构建右子树
        // 前序遍历：左子树之后的部分
        // 中序遍历：根节点之后的部分
        TreeNode right = dfs(preorder, preL + 1 + leftSize, preR,
                inL + 1 + leftSize, inR, index);

        // 创建当前根节点，连接左右子树
        return new TreeNode(rootVal, left, right);
    }
}
